package com.markus.code.newcode;

import com.markus.basic.Java基础.重写与重载.A;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/3 16:14
 * todo: 二叉树的三种遍历方式
 */
public class ThreeOrders {
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val){
            this.val = val;
        }
    }

    /**
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders(TreeNode root) {
        // write code here
        //前序遍历
        int[] preOrder = preOrder(root);
        int[] inOrder = inOrder(root);
        int[] aftOrder = aftOrder(root);
        int [][] ans = new int[3][preOrder.length];
        ans[0] = preOrder;
        ans[1] = inOrder;
        ans[2] = aftOrder;
        return ans;
    }

    private int[] preOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return getArr(list);
    }
    private int[] inOrder(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return getArr(list);
    }
    private int[] aftOrder(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> preStack = new Stack<>();
        Stack<TreeNode> aftStack = new Stack<>();
        preStack.push(root);
        while(!preStack.isEmpty()){
            TreeNode node = preStack.pop();
            aftStack.push(node);
            if(node.left != null){
                preStack.push(node.left);
            }
            if (node.right != null){
                preStack.push(node.right);
            }
        }
        while(!aftStack.isEmpty()){
            list.add(aftStack.pop().val);
        }
        return getArr(list);
    }
    private int[] getArr(List<Integer> list){
        int []arr= new int[list.size()];
        int index = 0;
        for (Integer integer : list) {
            arr[index++] = integer;
        }
        return arr;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        ThreeOrders demo = new ThreeOrders();
        int[][] ints = demo.threeOrders(root);
        for (int[] anInt : ints) {
            for (int i : anInt) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
}
